import java.util.*;
class TreeNode {
   int val = 0;
   TreeNode left = null;
   TreeNode right = null;
   public TreeNode(int val) {
     this.val = val;
   }
 }


public class Test {
    /*
    题目1：二叉搜索树的最近公共祖先
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if(root == null){
            return -1;
        } // 这段代码可要可不要，因为题目给的条件是 p 和 q 均存在于二叉搜索树中！

        // 利用 二叉搜索树的性质！！
        // 如果 p 和 q 的值在 root.val 的两边，那么公共祖先就是 root
        if((p <= root.val && q >= root.val) || (p >= root.val && q <= root.val)){
            return root.val;
        }else if(p <= root.val && q <= root.val){
            // p 和 q 同时在 左边
            // 进入左子树
            return lowestCommonAncestor(root.left, p, q);
        }else{
            // p 和 q 同时在右边
            // 进入右子树
            return lowestCommonAncestor(root.right, p, q);
        }
    }

    /*
    题目 2：在二叉树中找到两个节点的最近公共祖先
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        if(root == null){
            return -1;
        }

        if(root.val == o1 || root.val == o2){
            return root.val;
        }

        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);

        if(left == -1){
            return right;
        }

        if(right == -1){
            return left;
        }

        return root.val;
    }

    /*
    题目3：重建二叉树
     */
    public int i = 0;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        return buildChildTree(pre, vin, 0, vin.length - 1);
    }

    private TreeNode buildChildTree(int[] pre, int[] vin, int start, int end){
        if(start > end){
            return null;
        }

        int val = pre[i];
        i++;
        TreeNode root = new TreeNode(val);

        int index = findIndex(vin, val, start, end);

        root.left = buildChildTree(pre, vin, start, index - 1);
        root.right = buildChildTree(pre, vin, index + 1, end);

        return root;
    }

    private int findIndex(int[] vin, int key, int start, int end){
        for(int i = start; i <= end; i++){
            if(vin[i] == key){
                return i;
            }
        }
        return -1;
    }

    /*
    题目 4：输出二叉树的右视图
     */
    // 先利用前序遍历和中序遍历来建树
    // 之后是层序遍历，每一层的最后一个元素！
    public int[] solve (int[] xianxu, int[] zhongxu) {
        TreeNode tree = reConstructBinaryTree(xianxu, zhongxu);
        if(tree == null){
            return new int[]{};
        }

        Queue<TreeNode> queue = new LinkedList();
        queue.add(tree);

        List<Integer> list = new LinkedList<>();

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode temp = queue.poll();
                if(i == size - 1){
                    list.add(temp.val);
                }

                if(temp.left != null){
                    queue.add(temp.left);
                }

                if(temp.right != null){
                    queue.add(temp.right);
                }
            }
        }

        int[] res = new int[list.size()];

        for(int i = 0; i < list.size(); i++){
            res[i] = list.get(i);
        }

        return res;
    }
}
